package main.Q301_400;

public class Q331_340 {
    public static void main(String[] args) {
        System.out.println("Question331：");
        System.out.println("Question332：");
        System.out.println("Question333：");
        System.out.println("Question334：递增的三元子序列");
        System.out.println("Question335：");
        System.out.println("Question336：");
        System.out.println("Question337：打家劫舍Ⅲ");
        System.out.println("Question338：比特位计数");
        System.out.println("Question339：");
        System.out.println("Question340：");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Question334{
    public boolean increasingTriplet(int[] nums) {
        int length= nums.length;
        int[] leftMin=new int[length],rightMax=new int[length];
        for (int i=0;i<length;i++){//i位置左侧最小
            if (i==0||nums[i]<leftMin[i-1]) leftMin[i]=nums[i];
            else leftMin[i]=leftMin[i-1];
        }
        for (int i=length-1;i>=0;i--){//i位置右侧最大
            if (i==length-1||nums[i]>rightMax[i+1]) rightMax[i]=nums[i];
            else rightMax[i]=rightMax[i+1];
        }
        for (int i=0;i<length;i++){
            if (leftMin[i]<nums[i]&&nums[i]<rightMax[i]) return true;
        }
        return false;
    }
}

class Question337{
    class Info{
        int isSteal,unSteal;
        public Info(int isSteal,int unSteal){
            this.isSteal=isSteal;
            this.unSteal=unSteal;
        }
    }
    public Info process(TreeNode root){
        if (root==null) return new Info(0,0);//空节点
        int isSteal=0,unSteal=0;
        Info left=process(root.left);
        Info right=process(root.right);
        isSteal=left.unSteal+right.unSteal+root.val;//该节点被偷，下层节点未被偷
        unSteal=Math.max(left.isSteal,left.unSteal)+Math.max(right.isSteal,right.unSteal);//该节点未被偷，下层节点被偷
        return new Info(isSteal,unSteal);
    }
    public int rob(TreeNode root) {
        Info info = process(root);
        return Math.max(info.isSteal,info.unSteal);
    }
}

class Question338{
    public static int[] countBits(int n) {
        int[] count=new int[n+1];
        for (int i=0;i<=n;i++) count[i]=Integer.bitCount(i);
        return count;
    }
}